package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/maximum-subarray/description/
 */
public class P53 {

    //给你一个整数数组nums,请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];      //包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
        dp[0]=nums[0];
        int result=nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>result) result=dp[i];
        }
        return result;
    }


}
